// 给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。

// 示例：

// 输入: root = [4,2,6,1,3,null,null]
// 输出: 1
// 解释:
// 注意，root是树结点对象(TreeNode object)，而不是数组。

// 给定的树 [4,2,6,1,3,null,null] 可表示为下图:

//           4
//         /   \
//       2      6
//      / \    
//     1   3  

// 最小的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。
// 注意：

// 二叉树的大小范围在 2 到 100。
// 二叉树总是有效的，每个节点的值都是整数，且不重复。

#include "stdc++.h"

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 二叉搜索树中序遍历结果就是从小到大排序的数组，遍历数组
class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        int res = __INT_MAX__;
        vector<int> v{};
        func(root, v);
        for (int i{1}; i < v.size(); ++i) {
            res = min(res, v[i] - v[i-1]);
        }
        return res;
    }
    void func(TreeNode* node, vector<int>& v) {
        if (!node) return;
        func(node->left, v);
        v.push_back(node->val);
        func(node->right, v);
    }
};

class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        int res{INT_MAX};
        int pre{-1};
        dfs(root, pre, res);
        return res;
    }
    void dfs(TreeNode* root, int& pre, int& res) {
        if (root == nullptr) {
            return;
        }
        dfs(root->left, pre, res);
        if (pre != -1) {
            res = min(res, root->val - pre);
        }
        pre = root->val;
        dfs(root->right, pre, res);
    }
};

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        vector<int> nums;
        inOrder(root, nums);
        int result{INT_MAX};
        int n = nums.size();
        for (int i{1}; i < n; ++i) {
            result = min(result, nums[i] - nums[i-1]);
        }
        return result;
    }
private:
    void inOrder(TreeNode* root, vector<int>& nums) {
        if (nullptr == root) {
            return;
        }
        inOrder(root->left, nums);
        nums.push_back(root->val);
        inOrder(root->right, nums);
    }
};